﻿#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*

https://leetcode.cn/problems/maximum-product-subarray/


给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

 
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 

提示:
1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
*/


/*
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (tt == nums) return 1;
        int len = nums.size();
        nums.insert( nums.begin(),1);
        vector<int> sum(len + 1); sum[0] = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == 0) { sum[i] = 1; }
            else{  sum[i] = sum[i - 1] * nums[i];}
        }
        int ans = -99999999;
        for (int i = 0; i < nums.size(); i++) {
            if ((i + 1) < nums.size() && nums[i + 1] == 0) {
                ans = max(ans, 0); continue;
            }
            for (int j = i+1; j < nums.size(); j++) {
                if (nums[j] == 0 ) {
                    ans = max(ans, 0); break;
                }
                else if(ans  < sum[j] / sum[i]) {
                    ans = sum[j] / sum[i];
                }
            }
        }
       
        return ans;
    }
};
*/

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        nums.insert( nums.begin(),1 );
        int N = nums.size();
        vector<int> minDP(N, -0x3f3f3f3f);
        vector<int> maxDP(N, -0x3f3f3f3f);
        minDP[0] = 1; maxDP[0] = 1;
        int ret = -0x3f3f3f3f;
        for (int i = 1; i < nums.size(); i++) {
            int a = nums[i] * minDP[i - 1];
            int b = nums[i] * maxDP[i - 1];
            minDP[i] = min(nums[i],min(a, b));
            maxDP[i] = max(nums[i],max(a, b));
            ret = max(ret, maxDP[i]);
        }

        return  ret;
    }
};

//int main() {
//    Solution s;
//    vector<int> v{ 0,2 };
//    s.maxProduct(v);
//
//}